import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;


public class KnapsackBig {
	class Item{
		int value;
		int weight;
	}
	
	class SparseItem implements Comparable<SparseItem>{
		int index;
		int weight;
		int value;
		
		public int compareTo(SparseItem si)
		{
			if(this.weight > si.weight){
				return 1;
			}
			else if(this.weight == si.weight){
				return 0;
			}
			else{
				return -1;
			}
		}
	}
	int number;
	int size;
	ArrayList<Item> data;
	ArrayList<ArrayList<SparseItem>> sparseTable;
	
	
	public void InitData(){
		DataReader reader = new DataReader();
		reader.SetFilename("C:\\workspace\\testdata\\knapsack_big.txt");
		
		String str;
		str = reader.GetNextLine();
		String[] parser = str.split(" ");
		size = Integer.parseInt(parser[0]);
		number = Integer.parseInt(parser[1]);
		data = new ArrayList<Item>(number);
		
		while((str = reader.GetNextLine()) != null)
		{
			parser = str.split(" ");
			Item item = new Item();
			item.value = Integer.parseInt(parser[0]);
			item.weight = Integer.parseInt(parser[1]);
			data.add(item);
		}
	}
	
	public ArrayList<SparseItem> CreateNextRow(){
		
		ArrayList<SparseItem> sparseRow = new ArrayList<SparseItem>();
		
		return sparseRow;
	}
	
	public int GetLastItem(int weight, ArrayList<SparseItem> row){
		if(weight < 0)
			return -size;
		
		int ret = 0;
		for(int i = 0; i < row.size(); i++)
		{
			//find item with index "index"
			SparseItem si = row.get(i);
			if(si.weight <= weight){
				ret = si.value;
			}
			else{
				break;
			}
		}
		
		return ret;
	}
	
	public int GetMaxValueFromLastRow(SparseItem item, Item vertex, ArrayList<SparseItem> row){
		//A(i - 1, w)
		int v1 = GetLastItem(item.weight, row);
		
		//A(i-1, w-wi) + vi
		int v2 = GetLastItem(item.weight - vertex.weight, row) + vertex.value;
		
		if(v1 >= v2)
			return v1;
		else
			return v2;
	}
	
	
	public SparseItem GetItemByIndexWeight(int index, int weight, ArrayList<SparseItem> row){
		SparseItem findItem = null;
		for(int i = 0; i < row.size(); i++)
		{
			SparseItem item = row.get(i);
			if(item.index == index && item.weight == weight){
				findItem = item;
				break;
			}
		}
		
		return findItem;
	}
	
	public void ComputeItemInNextRow(SparseItem si, ArrayList<SparseItem> curRow, ArrayList<SparseItem> nextRow, Item vertex)
	{
		SparseItem newItem = GetItemByIndexWeight(si.index + 1, si.weight, nextRow);
		if(newItem == null)
		{
			newItem = new SparseItem();
			newItem.index = si.index + 1;
			newItem.weight = si.weight;
			newItem.value = GetMaxValueFromLastRow(newItem, vertex, curRow);		
			nextRow.add(newItem);
		}
		else
		{
			int value = GetMaxValueFromLastRow(newItem, vertex, curRow);
			if(value > newItem.value)
				newItem.value = value;
		}
		
		if(si.weight + vertex.weight <= size){
			newItem = GetItemByIndexWeight(si.index + 1, si.weight + vertex.weight, nextRow);
			if(newItem == null)
			{
				newItem = new SparseItem();
				newItem.index = si.index + 1;
				newItem.weight = si.weight + vertex.weight;
				newItem.value = GetMaxValueFromLastRow(newItem, vertex, curRow);		
				nextRow.add(newItem);
			}
			else
			{
				int value = GetMaxValueFromLastRow(newItem, vertex, curRow);
				if(value > newItem.value)
					newItem.value = value;
			}	
		}
		
	}
	
	
	public void PrintData(ArrayList<SparseItem> row){
		
		for(int i = 0; i < row.size(); i++){
			SparseItem si = row.get(i);
			System.out.println(si.index + "\t" + si.weight + "\t" + si.value);
		}
		
	}
	
	public void RunKnapSackBig(){
		//sparseTable = new ArrayList<ArrayList<SparseItem>>(number + 1);
		ArrayList<SparseItem> curRow = CreateNextRow();
		SparseItem si = new SparseItem();
		si.index = 0;
		si.weight = 0;
		si.value = 0;
		curRow.add(si);
		ArrayList<SparseItem> nextRow = CreateNextRow();
		
		for(int i = 0; i < number; i++){
			Item vertex = data.get(i);
			for(int j = 0; j < curRow.size(); j++){
				si = curRow.get(j);
				ComputeItemInNextRow(si, curRow, nextRow, vertex);
				//sort nextRow by weight;
				Collections.sort(nextRow);
			}
			curRow = nextRow;
			System.out.println(i);
			nextRow = CreateNextRow();
		}
		
		int last = curRow.size() - 1;
		SparseItem maxItem = curRow.get(last);
		System.out.println("Optimal value is " + maxItem.value);
	}
	
	
	
	public int GetValueFromPreRow(int []pre, int weight, Item vertex){
		int v1 = pre[weight];
		if(weight - vertex.weight < 0)
			return v1;
		
		int v2 = pre[weight - vertex.weight] + vertex.value;
		
		if(v1 > v2)
			return v1;
		else 
			return v2;
	}
	
	public void PrintCurrentTime(String strPrefix){
		System.out.println(strPrefix);
		SimpleDateFormat sf = new SimpleDateFormat("HH:mm:ss.SSS");
		System.out.println(sf.format(new Date()));
	}
	
	public void RunKnapSackBig2(){
		this.PrintCurrentTime("start");
		int[] pre = new int[size + 1];
		int[] cur = new int[size + 1];
		
		for(int i = 0; i < number; i++){
			Item vertex = data.get(i);
			for(int j = 0; j < size + 1; j++){
				cur[j] = GetValueFromPreRow(pre, j, vertex);
				//System.out.print(cur[j] + "\t");	
			}
			int []temp = pre;
			pre = cur;
			cur = temp;
			//System.out.print("\n");
			//System.out.println(i);
		}
		cur = pre;
		
		System.out.println("Optimal value is " + cur[size]);
		this.PrintCurrentTime("end");
	}
}
